//给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

//用到的算法
//1. 回溯法
//2. 动态规划
//3. 回溯法 + 动态规划
// var permute = function(nums) {
//   const res = [], path = [];  // 存储结果
//   backtracking(nums, nums.length, []);  // 回溯 []是dp数组 "dp[i]是否地用过"
//   backtracking(nums,"从最后一个开始->往前回溯", []是dp数组 "dp[i]是否地用过");  // 回溯 
//   return res; // 返回结果
//
//   function backtracking(n, k, used) {   // 回溯函数
//     if(path.length === k) { // 如果路径长度等于数组长度，则添加路径到结果中
//       res.push(Array.from(path)); // 深拷贝
//       return;
//     }
//     for (let i = 0; i < k; i++ ) {  // 对于数组中的每个数字
//       if(used[i]) continue; // 如果该数字已经被使用，则跳过
//       path.push(n[i]);  // 将该数字添加到路径中
//       used[i] = true; // 同支 将该数字标记为已使用  下次不会重复使用
//       backtracking(n, k, used); // 回溯
//       //回溯算法的核心在于回溯访问之前要将相应的状态归位，即将路径中的最后一个数字移除，并将该数字标记为未使用
//       path.pop(); // 回溯时，将该数字从路径中移除
//       used[i] = false;  // 回溯时，将该数字标记为未使用
//       // https://blog.csdn.net/weixin_43314519/article/details/107797531
//     }
//   }
// };
// const permute = (nums) => {
//   const res = [];
//   const used = {};
//
//   function dfs(path) {
//     if (path.length == nums.length) { // 个数选够了
//       res.push(path.slice()); // 拷贝一份path，加入解集res
//       return;                 // 结束当前递归分支
//     }
//     for (const num of nums) { // for枚举出每个可选的选项
//       // if (path.includes(num)) continue; // 别这么写！查找是O(n)，增加时间复杂度
//       if (used[num]) continue; // 使用过的，跳过
//       path.push(num);         // 选择当前的数，加入path
//       used[num] = true;       // 记录一下 使用了
//       dfs(path);              // 基于选了当前的数，递归
//       path.pop();             // 上一句的递归结束，回溯，将最后选的数pop出来
//       used[num] = false;      // 撤销这个记录
//     }
//   }
//
//   dfs([]); // 递归的入口，空path传进去
//   return res;
// };
//
var permute = function(nums) {
    let res = [], path = [];
    backtracking(nums, nums.length, []);
    return res;
    function backtracking(n, k, used) {
        if (path.length === k) {
            res.push(Array.from(path));
            return;
        }
        for (var i = 0; i < k; i++) {
            if (used[i]) {
                continue;
            }
            path.push(n[i]);
            used[i]=true;
            backtracking(n, k, used);
            used[i] = false;
            path.pop();
        }
    }
  };
console.log(permute([1,2,3,4]));

